#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include "plist.h"
#include "network.h"
#include "edge.h"
#include "node.h"
#include <err.h>
#include "uthash.h"

#define min( a, b ) ( ((a) < (b)) ? (a) : (b) ) /*!< Funcion minimo */

/*! @struct s_network
 *  @brief Esta estructura representa un network.
 *  @param hash Hash table de nodos
 */
struct s_network {
	node hash;
};

network network_create(void){
	network net = NULL;
	net = malloc(sizeof(struct s_network));
    if (net == NULL)
        errx(EXIT_FAILURE, "Memoria insuficiente\n");
	net->hash = NULL;
	return net;
}

node network_find(network n, unsigned int name){
    node nd = NULL;
    assert(n != NULL);
    HASH_FIND_INT( n->hash, &name, nd );
    return nd;
}

void network_add(network n, unsigned int from, unsigned int to, 
                    unsigned  int cap, unsigned int flow){
                        
    node nd_from = NULL;
    node nd_to = NULL;
    edge egxy = NULL;
    edge egyx = NULL;
    edge e = NULL;
    unsigned int name = 0;
    assert(n != NULL);
    
    /* Busco los nodos origen y destino en el network, pueden no 
     * haberse creado aun*/
    HASH_FIND_INT( n->hash, &from, nd_from );
    HASH_FIND_INT( n->hash, &to, nd_to );
    
    /* Si el nodo origen no está, lo creo */
    if (nd_from == NULL){
        nd_from = node_create(from);
        if (nd_from == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
        name = from;
        HASH_ADD_INT( n->hash, name, nd_from );
    }
    
    /* Si el nodo destino no está, lo creo */
    if (nd_to == NULL){
        nd_to = node_create(to);
        if (nd_to == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
        name = to;
        HASH_ADD_INT( n->hash, name, nd_to );
    }
    
    /* Veo si ya existe la arista, en ese caso mostramos el error
     *  y terminamos */
    e = edge_find_node_forw(nd_from,nd_to);
    if (e != NULL)
        errx(EXIT_FAILURE, "Ya existe la arista %d %d",node_name(nd_from),node_name(nd_to));
        
    /*Creo la arista correspondiente a los nodos*/
    egxy = edge_create(nd_to,cap,flow,false);
    if (egxy == NULL)
        errx(EXIT_FAILURE, "Memoria insuficiente\n");
        
    egyx = edge_create(nd_from,cap,flow,true);
    if (egyx == NULL)
        errx(EXIT_FAILURE, "Memoria insuficiente\n");
        
    /* Agrego la arista a la lista de vecinos del nodo origen */
    plist_append(node_neighbours(nd_from),egxy);
    plist_append(node_neighbours(nd_to),egyx);
}

void network_destroy(network n){
    node current, tmp;
    assert(n != NULL);
    /* Este macro itera sobre todos los elementos del hash */
    HASH_ITER(hh, n->hash, current, tmp) {
        /* Borramos del hash el nodo y liberamos el nodo*/
        HASH_DEL(n->hash,current);  
        node_destroy(current);            
    }
    free(n);

}

void network_helper_add(network n, unsigned int from, unsigned int to,
                        unsigned  int cap, unsigned int flow, 
                        bool backward){
                            
    node nd_from = NULL;
    node nd_to = NULL;
    edge eg = NULL;
    unsigned int name = 0;
    assert(n != NULL);
    
    /* Busco los nodos origen y destino en el network, pueden no 
     * haberse creado aun*/
    HASH_FIND_INT( n->hash, &from, nd_from );
    HASH_FIND_INT( n->hash, &to, nd_to );
    
    /* Si el nodo origen no está, lo creo */
    if (nd_from == NULL){
        nd_from = node_create(from);
        if (nd_from == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
            
        name = from;
        HASH_ADD_INT( n->hash, name, nd_from );
    }
    
    /* Si el nodo destino no está, lo creo */
    if (nd_to == NULL){
        nd_to = node_create(to);
        if (nd_to == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
            
        name = to;
        HASH_ADD_INT( n->hash, name, nd_to );
    }
    
    if (!backward){
        /*Creo la arista correspondiente a los nodos*/
        eg = edge_create(nd_to,cap,flow,backward);
        if (eg == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
            
        /* Agrego la arista a la lista de vecinos del nodo origen */
        plist_append(node_neighbours(nd_from),eg);
    }
    if (backward){
        /*Creo la arista correspondiente a los nodos*/
        eg = edge_create(nd_to,cap,flow,backward);
        if (eg == NULL)
            errx(EXIT_FAILURE, "Memoria insuficiente\n");
            
        /* Agrego la arista a la lista de vecinos del nodo origen */
        plist_append(node_neighbours(nd_from),eg);
    }
}

network network_helper_create(network n){

	network network_helper = NULL;
    node nd = NULL;
    node nd_to = NULL;
    node first = NULL;
    node tmp = NULL;
    node nd_source = NULL;
    edge e = NULL;
    plist_t neighbours;
    plist_t queue;
    unsigned int source = SOURCE;
    unsigned int name = 0;
    int level = 1;
    assert(n != NULL);
	network_helper = network_create();
    
    HASH_FIND_INT( n->hash, &source, nd);
    assert(nd!=NULL);
    
    /* El s siempre está en el corte por lo que lo agregamos*/
    nd_source = node_create(source);
    name = source;
    HASH_ADD_INT(network_helper->hash, name, nd_source);

    queue = plist_create();
    
    /* Encolamos el s y le ponemos nivel 1*/
    plist_append(queue, nd);
    node_visit(nd);
    node_set_level(nd,1);
    
    while(!plist_is_empty(queue)){
        
        /* Tomo el primer nodo de la cola */
        first = plist_pop(queue);
        
        /* Si el nodo tiene un nivel mayor que el actual entonces 
         * hay que incrementar el nivel actual*/
        if (node_get_level(first) > level)
            level++;
            
        /* Sacamos la lista de vecinos del primer nodo de la cola*/
        neighbours = node_neighbours(first);
        e = plist_get_next(neighbours);
        
        /* Recorremos y vamos agregando a los vecinos del primer nodo*/
        while (e != NULL){
                nd_to = edge_to(e);
                if (!node_visited(nd_to) || 
                    node_get_level(nd_to) > level){
                    
                    /* Si es forward y hay flujo disponible, agrego */
                    if (!edge_get_backward(e) && 
                        edge_get_capacity(e)-edge_get_flow(e) > 0){
                            
                        if (!node_visited(nd_to)){
                            node_visit(nd_to);
                            node_set_level(nd_to,level+1);
                            plist_append(queue, nd_to);
                        }
                        network_helper_add(network_helper,
                                            node_name(first),
                                            node_name(nd_to),
                                            edge_get_capacity(e),
                                            edge_get_flow(e),
                                            false);
                    }
                    
                    /* Si es backward y ya mandamos algo, agrego*/
                    if (edge_get_backward(e) && edge_get_flow(e) > 0){
                        if (!node_visited(nd_to)){
                            node_visit(nd_to);
                            node_set_level(nd_to,level+1);

                            plist_append(queue, nd_to);
                        }                        
                        network_helper_add(network_helper,
                                            node_name(first),
                                            node_name(nd_to),
                                            edge_get_capacity(e),
                                            edge_get_flow(e),
                                            true);
                    }
                }
                
                /* Avanzo al próximo vecino*/
                e = plist_get_next(neighbours);
        }
        plist_rewind(neighbours);
    }
    plist_destroy(&queue);
       
    /* Ahora recorremos todos los nodos nuevamente para desvisitarlos
     * y resetear el nivel */
    HASH_ITER(hh, n->hash, nd, tmp) {
        node_unvisit(nd);
        node_set_level(nd,LEVEL_CLEAR);  
    }
        
	return network_helper;
}



bool network_path_exists(network n){
    unsigned int sink = SINK;
    node nd = NULL;
    bool ret = true;
    
    assert(n != NULL);
    
    /* Busco t en el network*/
    HASH_FIND_INT( n->hash, &sink, nd );
    
    /* Si t no está, entonces no hay camino hasta t*/
    if (nd == NULL)
        ret = false;
        
    return ret;
}

void network_cut_calculate(network n){
    int elements = 0;
    int i = 0;
    FILE *f = NULL;
    assert(n != NULL);
    f = fopen("cut.txt","w");
    
    /* Calculo la cantidad de elementos del hash */
    elements = HASH_COUNT(n->hash);

    fprintf(f,"Corte: {");
    
    /* Si tiene un solo elemento*/
    if (elements == 1){
        fprintf(f,"%u", n->hash->name);
        fprintf(f,"}\n");
        fclose(f);
        return;
    }
    
    /* Itero sobre todos los nodos del network auxiliar */
    for(i=0;i<elements-1;i++){
        fprintf(f,"%u, ", n->hash->name);
        
        /* Avanzo al proximo nodo del network auxiliar */
        n->hash = n->hash->hh.next;
    }
    
    fprintf(f,"%u", n->hash->name);
    fprintf(f,"}\n");
    fclose(f);
}

void network_flow_calculate(network n){
    node nd, tmp;
    FILE *f = NULL;
    unsigned int node_from = 0;
    unsigned int node_to = 0;
    edge e = NULL;
    plist_t neighbours = NULL;
    assert(n != NULL);
    
    f = fopen("flow.txt","w");
    fprintf(f,"Flujo Maximal:\n");
    
    /* Itero sobre todos los nodos del network */
    HASH_ITER(hh, n->hash, nd, tmp){
        node_from = node_name(nd);
        
        /*Calculo la lista de vecinos del nodo*/
        neighbours = node_neighbours(nd);
        e = plist_get_next(neighbours);
        
        /* Itero sobre todos los vecinos de cada nodo del network */
        while (e != NULL){
                if (!edge_get_backward(e)){
                    node_to = node_name(edge_to(e));
                    
                    /* Imprimo x y flujo capacidad*/
                    fprintf(f,"%u\t%u\t%u (%u)\n",node_from,
                                                    node_to,
                                                    edge_get_flow(e),
                                                    edge_get_capacity(e));
                }
                    /* Avanzo al próximo vecino */
                    e = plist_get_next(neighbours);
        }
    }
    plist_rewind(neighbours);
    fprintf(f,"\n");

    fclose(f);
}

unsigned int network_max_flow_calculate(network n){
    node nd;
    unsigned int source = SOURCE;
    unsigned int max_flow = 0;
    edge e = NULL;
    plist_t neighbours = NULL;
    
    /* Busco el nodo s*/
    HASH_FIND_INT( n->hash, &source, nd );
    neighbours = node_neighbours(nd);
    e = plist_get_next(neighbours);
    
    /* Calculo la suma de los flujos de los vecinos de s*/
    while (e != NULL){
            max_flow += edge_get_flow(e);
            e = plist_get_next(nd->neighbours);
    }
    plist_rewind(neighbours);
    return max_flow;

}

void network_increase_flow(plist_t path, 
                        network n, 
                        unsigned int min_flow){
                            
    node x = NULL;
    node y = NULL;
    edge e = NULL;
    unsigned int name = 0;
    assert(n != NULL);
    assert(path != NULL);

    plist_rewind(path);
    x = plist_get_next(path);
    
    /* Recorro los nodos del camino*/
    while (x != NULL){
            name = node_name(x);
            HASH_FIND_INT( n->hash, &name, x);
            
            /* Tomo el nodo siguiente en el camino*/
            y = plist_get_next(path);
            
            /* Si es NULL ya terminamos con el camino*/
            if (y == NULL)
                break;
                
            /* Busco la arista xy */
            e = edge_find_node_forw(x,y);
            
            /* Si la arista existe*/
            if (e != NULL){
                
                /* Cambiamos el flujo de xy y de xy */
                edge_set_flow(e, edge_get_flow(e) + min_flow);
                name = node_name(y);
                HASH_FIND_INT( n->hash, &name, y);
                e = edge_find_node_back(y,x);
                edge_set_flow(e, edge_get_flow(e) + min_flow);
            }
            
            /* No estaba el lado xy, porque en realidad es yx.*/
            else{
                
                /* Es backward entonces restamos el flujo en xy, yx*/
                name = node_name(y);
                HASH_FIND_INT( n->hash, &name, y);
                e = edge_find_node_forw(y,x);
                edge_set_flow(e, edge_get_flow(e) - min_flow);
                
                e = edge_find_node_back(x,y);
                edge_set_flow(e, edge_get_flow(e) - min_flow);
            }
            
            /* Avanzo el pivote al siguiente nodo */
            x = y;

    }
}

unsigned int network_helper_increase_flow(plist_t path, network n){
    node x = NULL;
    node y = NULL;
    edge e = NULL;
    unsigned int name = 0;
    unsigned int min_flow = NOT_DEFINED;
    assert(n != NULL);
    assert(path != NULL);
    
    
    plist_rewind(path);
    x = plist_get_next(path);
    /* Recorro los nodos del camino para encontrar el mínimo flujo 
     * del camino*/
    while (x != NULL){
            name = node_name(x);
            HASH_FIND_INT( n->hash, &name, x);
            
            /* Tomo el segundo nodo del camino */
            y = plist_get_next(path);
            
            /* Si es NULL es porque se termino el camino*/
            if (y==NULL){
                break;
            }
            
            /* Busco el lado xy en fordward*/
            e = edge_find_node_forw(x,y);
            if (e != NULL){
                if (min_flow == NOT_DEFINED)
                    min_flow = edge_get_capacity(e) - edge_get_flow(e);
                else
                    min_flow = min(min_flow,  
                                    edge_get_capacity(e) - edge_get_flow(e));
            }
            
            /* Si no está, busco el lado xy en backward*/
            else{
                e = edge_find_node_back(x,y);
                if (min_flow == NOT_DEFINED)
                    min_flow = edge_get_flow(e);
                else
                    min_flow = min(min_flow, edge_get_flow(e));
            }
            
            /* Avanzo al proximo nodo del camino*/
            x = y;
    }

    plist_rewind(path);
    x = plist_get_next(path);
    
    /* Recorro los nodos del camino nuevamente, pero ahora para
     * actualizar los flujos*/
    while (x != NULL){
            name = node_name(x);
            HASH_FIND_INT( n->hash, &name, x);
            y = plist_get_next(path);
            if (y==NULL)
                break;
            e = edge_find_node_forw(x,y);
            if (e != NULL){
                edge_set_flow(e, edge_get_flow(e) + min_flow);
            }
            else{
                e = edge_find_node_back(x,y);
                edge_set_flow(e, edge_get_flow(e) - min_flow);
            }
            x = y;

    }
    return min_flow;
}




